package kyssion.leetcode.num51_100;

import kyssion.leetcode.util.ShowUtil;
import kyssion.leetcode.util.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class code94_二叉树中序遍历 {

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.create(new int[]{
                1, 2, 3
        });
        ShowUtil.showList(new code94_二叉树中序遍历().inorderTraversal2(treeNode), true);
    }

    /**
     * 使用递归算法求解
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        ans(list, root);
        return list;
    }

    public void ans(List<Integer> list, TreeNode root) {
        if (root == null) {
            return;
        }

        ans(list, root.left);
        list.add(root.val);
        ans(list, root.right);
        return;
    }

    /**
     * 使用迭代算法求解
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode item = stack.peek();
            if (item.left != null) {
                stack.push(item.left);
            } else {
                list.add(item.val);
                stack.pop();
                if (item.right != null) {
                    stack.push(item.right);
                } else {
                    if(!stack.empty()){
                        stack.peek().left=null;
                    }
                }
            }
        }
        return list;
    }
}
